1. Field of the Invention
The present invention relates to a technique for extracting a fixed pattern in which a plurality of fixed pattern elements are arranged from a writing pattern in which a plurality of writing pattern elements are arranged to be written on a substrate and also relates to a pattern writing apparatus for writing a pattern on the substrate.
2. Description of the Background Art
In recent years, with high integration of LSIs (Large Scale Integrated Circuits) formed on a semiconductor substrate (hereinafter, referred to as “substrate”), a pattern writing apparatus (also referred to as “electron beam exposure apparatus”) for emitting an electron beam to write a pattern has come into use. In the pattern writing apparatus, each of a plurality of writing pattern elements representing a writing pattern to be written on a substrate is divided into a plurality of rectangle pattern elements, and writing is performed while a sectional shape of electron beam is changed in accordance with each of a plurality of divided pattern elements. For a speed-up of writing in the pattern writing apparatus, a technique (character projection) is being adopted, in which a mask having an opening pattern in conformity with a predetermined fixed polygonal element is prepared and the fixed polygonal element in the writing pattern is written by using the mask.
The character projection requires an operation of extracting a fixed polygonal element from a writing pattern in which a plurality of writing pattern elements are arranged. Japanese Patent No. 3266327 (Document 1), for example, discloses a technique where if respective incoming vectors and outgoing vectors of a predetermined reference point of a fixed polygonal element and a given vertex of a writing pattern element coincide with each other, this vertex of the writing pattern element is determined as a candidate point and respective position vectors of remaining vertices with the reference point of the fixed polygonal element as a point of origin are calculated, and if remaining vertices of the writing pattern element exist at positions specified by the position vectors with the candidate point of the writing pattern element as a point of origin and the number of vertices of the fixed polygonal element and that of the writing pattern element coincide with each other, this writing pattern element is extracted as the fixed polygonal element.
For further speed-up of writing in the pattern writing apparatus, it is preferable that a fixed pattern in which a plurality of fixed pattern elements are arranged should be written by using a mask at a time (at a plurality of times, depending on the size of the fixed pattern). It is not easy, however, to extract a fixed pattern in which a plurality of fixed pattern elements are arranged from a writing pattern, and even if all the combinations of writing pattern elements in the writing pattern are detected to be compared with the fixed pattern, it takes a long time to perform such an operation. Also by the method of Document 1, it is not possible to extract a plurality of fixed pattern elements from a writing pattern, in consideration of positional relation of the fixed pattern elements.
In a case where a writing pattern is represented by a data structure consisting of hierarchical structures (also referred to as cells), which indicate the kinds of shapes of writing pattern elements and their layout, if a name of a structure coincident with a fixed pattern represented by an opening pattern on a mask is already known, it is possible to extract the fixed pattern from the writing pattern on the basis of the name of the structure, but if a name of a structure in an inputted writing pattern, which corresponds to an opening pattern on a mask, is not known, (for example, when a writing pattern named in accordance with a naming rule different from a naming rule used in mask formation is inputted), it is not possible to extract a fixed pattern from the writing pattern.